//一和零
class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m+1,vector<int>(n+1));

        for(size_t i = 1 ; i <= strs.size() ; ++i)
        {
            for(int j = m ; j >= 0 ; --j)
            {
                for(int k  = n ; k >= 0 ; --k)
                {
                    int a = 0 , b = 0;
                    for(auto& ch : strs[i-1])
                    {
                        if(ch == '0') a++;
                        else b++;
                    }
                    if(j-a >= 0 && k - b >= 0 && dp[j-a][k-b]+1 > dp[j][k]) dp[j][k]=dp[j-a][k-b]+1;
                }
            }
        }
        return dp[m][n];
    }
};

//盈利计划
class Solution {
public:
    const static int val = 1000000007;
    int profitableSchemes(int n, int minProfit, vector<int>& group,
                          vector<int>& profit) {
        vector<vector<int>> dp(n + 1, vector<int>(minProfit + 1));
        for(size_t i = 0 ; i <= n ; ++i) dp[i][0] = 1;
        for (size_t k = 0; k < group.size(); ++k) {
            for (int i = n; i >= 0; --i) {
                for (int j = 0; j <= minProfit; ++j) {
                    if (i - group[k] >= 0)
                        dp[i][j] += (dp[i - group[k]][max(0,  j - profit[k])]%val);
                        dp[i][j] %= val;
                }
            }
        }
        return dp[n][minProfit];
    }
};